package cn.rocky.prepare;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 1475. 商品折扣后的最终价格
 */
public class finalPrices {

    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int discount = 0;
            for (int j = i + 1; j < n; j++) {
                if (prices[j] <= prices[i]) {
                    discount = prices[j];
                    break;
                }
            }
            ans[i] = prices[i] - discount;
        }
        return ans;
    }

    public int[] finalPrices1(int[] prices) {
        int n = prices.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; i--) {
           while (!stack.isEmpty() && stack.peek() > prices[i]) {
               stack.pop();
           }
           ans[i] = stack.isEmpty() ? prices[i] : prices[i] - stack.peek();
           stack.push(prices[i]);
        }
        return ans;
    }

}
